//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "type_traits.h"
#include "iterator_traits.h"

#include <string.h>
#include <new>

#ifdef _MSC_VER
	#pragma warning ( push )
	#pragma warning ( disable : 4100 ) //bogus unreferenced parameter warning
#endif

FC_NAMESPACE_BEGIN


namespace internal
{

	FC_FORCE_INLINE void* mem_copy( const void* first, const void* last, void* result )
		{
			const size_t n = size_t((const char*)last - (const char*)first);
			return n ? (void*)
				((char*)::memcpy( result, first, n ) + n) : result;
		}

	FC_FORCE_INLINE void* mem_move( const void* first, const void* last, void* result )
		{
			const size_t n = size_t((const char*)last - (const char*)first);
			return n ? (void*)
				((char*)::memmove( result, first, n ) + n) : result;
		}

	template <class T> FC_FORCE_INLINE
		bool mem_cmp( const T* ptr1, const T* ptr2, size_t n )
		{
			return ::memcmp( (void*)ptr1, (void*)ptr2, n ) == 0 ? true : false;
		}

	template <class T> FC_FORCE_INLINE
		const T* mem_chr( const T* first, const T* last, T c )
		{
			const T* ret = last;
			const size_t n = (last - first) * sizeof(T);
			if( n > 0 )
				ret = (const T*)::memchr( first, c, n );

			return (ret ? ret : last);
		}

	template <class ForwardIterator, class T> inline
		void construct_n( ForwardIterator first, size_t n, const T& value, true_type )
		{
			::memset( first, value, n * sizeof(T) );
		}

	template <class ForwardIterator, class T> inline
		void construct_n( ForwardIterator first, size_t n, const T& value, false_type )
		{
			for( ; n--; ++first )
				new (&*first) T(value);
		}

	template <class T> inline
		void destroy( T*, true_type )
		{
			//do nothing
		}

	template <class T> inline
		void destroy( T* ptr, false_type )
		{
			ptr->~T();
		}

	template <class Iter> inline
		void destroy_range( Iter, Iter, true_type )
		{
			//do nothing
		}

	template <class BidirectionalIterator> FC_FORCE_INLINE
		void destroy_range( BidirectionalIterator first, BidirectionalIterator last, false_type )
		{
			typedef typename fc::iterator_traits<BidirectionalIterator>::value_type value_type;
			while( first != last )
				(--last)->~value_type();
		}

	template <class T> inline
		void destroy_n( T*, size_t, true_type )
		{
			//do nothing
		}

	template <class T> inline
		void destroy_n( T* ptr, size_t n, false_type )
		{
			for( size_t i(n); i != 0; )
				(ptr + --i)->~T();
		}

	// uninitialized copy algorithms

	template <class Iter, class T> inline
		T* uninitialized_copy( Iter first, Iter last, T* result, true_type )
		{
			return (T*)mem_copy( (void*)first, (void*)last, (void*)result );
		}

	template <class InputIterator, class ForwardIterator> inline
		ForwardIterator uninitialized_copy( InputIterator first, InputIterator last, ForwardIterator result, false_type )
		{
			typedef typename fc::iterator_traits<ForwardIterator>::value_type value_type;
			for( ; first != last; ++first, ++result )
				new (&*result) value_type(*first);
			return result;
		}

	template <class Iter, class T> inline
		T* uninitialized_copy_backward( Iter first, Iter last, T* result, true_type )
		{
			ptrdiff_t n = ptrdiff_t(last - first);
			return (T*)((char*)mem_move( (void*)first, (void*)last, (void*)(result - n) ) - n);
		}

	template <class InputIterator, class ForwardIterator> inline
		ForwardIterator uninitialized_copy_backward( InputIterator first, InputIterator last, ForwardIterator result, false_type )
		{
			typedef typename fc::iterator_traits<ForwardIterator>::value_type value_type;
			while( first != last )
				new (&*--result) value_type(*--last);
			return result;
		}

	template <class ForwardIterator, class T> inline
		void uninitialized_fill( ForwardIterator first, ForwardIterator last, const T& value, true_type )
		{
			for( ; first != last; ++first )
				*first = value;
		}

	template <class ForwardIterator, class T> inline
		void uninitialized_fill( ForwardIterator first, ForwardIterator last, const T& value, false_type )
		{
			for( ; first != last; ++first )
				new (&*first) T(value);
		}


} //internal


// construct

template <class T> FC_FORCE_INLINE
	void construct( T* ptr )
	{
		new (ptr) T;
	}

template <class T> FC_FORCE_INLINE
	void construct( T* ptr, const T& value )
	{
		new (ptr) T(value);
	}


// construct_n

template <class T> FC_FORCE_INLINE
	void construct_n( T* ptr, size_t n, const T& value = T() )
	{
		//internal::construct_n( ptr, n, value, typename has_trivial_constructor<T>::type() );
		return internal::construct_n( ptr, n, value,
			typename is_binary_copyable< is_sizeof<T, 1>::value, true >::type() );
	}


// destroy

template <class T> FC_FORCE_INLINE
	void destroy( T* ptr )
	{
		internal::destroy( ptr, typename has_trivial_destructor<T>::type() );
	}


// destroy_range

template <class BidirectionalIterator> FC_FORCE_INLINE
	void destroy_range( BidirectionalIterator first, BidirectionalIterator last )
	{
		internal::destroy_range( first, last,
			typename has_trivial_destructor< typename iterator_traits<BidirectionalIterator>::value_type >::type() );
	}


// destroy_n

template <class BidirectionalIterator> FC_FORCE_INLINE
	void destroy_n( BidirectionalIterator first, size_t n )
	{
		internal::destroy_range( first, first + n,
			typename has_trivial_destructor< typename iterator_traits<BidirectionalIterator>::value_type >::type() );
	}


// uninitialized_copy

template <class InputIterator, class ForwardIterator> FC_FORCE_INLINE
	ForwardIterator uninitialized_copy( InputIterator first, InputIterator last, ForwardIterator result )
	{
		return internal::uninitialized_copy( first, last, result, typename is_binary_copyable<
				is_pointer<InputIterator>::value, is_pointer<ForwardIterator>::value,
				has_trivial_copy< typename fc::iterator_traits<InputIterator>::value_type >::value,
				has_trivial_copy< typename fc::iterator_traits<ForwardIterator>::value_type >::value
			>::type()
		);
	}


// uninitialized_copy_backward

template <class InputIterator, class ForwardIterator> FC_FORCE_INLINE
	ForwardIterator uninitialized_copy_backward( InputIterator first, InputIterator last, ForwardIterator result )
	{
		return internal::uninitialized_copy_backward( first, last, result, typename is_binary_copyable<
				is_pointer<InputIterator>::value, is_pointer<ForwardIterator>::value,
				has_trivial_copy< typename fc::iterator_traits<InputIterator>::value_type >::value,
				has_trivial_copy< typename fc::iterator_traits<ForwardIterator>::value_type >::value
			>::type()
		);
	}


// uninitialized_fill

template <class ForwardIterator, class T> FC_FORCE_INLINE
	void uninitialized_fill( ForwardIterator first, ForwardIterator last, const T& value )
	{
		internal::uninitialized_fill( first, last, value, typename has_trivial_copy<T>::type() );
	}


// uninitialized_fill_n

template <class ForwardIterator, class T> FC_FORCE_INLINE
	void uninitialized_fill_n( ForwardIterator first, size_t n, const T& value = T() )
	{
		//internal::construct_n( first, n, value, typename has_trivial_constructor<T>::type() );
		internal::construct_n( first, n, value, typename is_binary_copyable<
			is_pointer<ForwardIterator>::value, is_sizeof<T, 1>::value,
			is_sizeof< typename iterator_traits<ForwardIterator>::value_type, 1 >::value
			>::type()
		);
	}


// align

inline size_t align( size_t size, size_t alignment = FC_DEFAULT_ALIGN )
	{
		return (alignment > 1) ? ((size + (alignment - 1)) & ~(alignment - 1)) : size;
	}

inline void* align( void* p, size_t alignment = FC_DEFAULT_ALIGN )
	{
		//return (void*)align((size_t)p, alignment);
		return (alignment > 1) ? (void*)(((size_t)p + (alignment - 1)) & ~(alignment - 1)) : p;
	}



// We require these functions to be user-defined as this library will never
// allocate any memory, especially without the users consent.

extern FC_API void* allocate( size_t n, size_t /*alignment*/ = 0 );
extern FC_API void deallocate( void* p, size_t /*size*/ = 0 );

#if FC_TEMPORARY_MEMORY_ENABLED
	extern FC_API void* allocate_temporary( size_t n, size_t /*alignment*/ = 0 );
	extern FC_API void deallocate_temporary( void* p, size_t /*size*/ = 0 );
#else
	void* allocate_temporary( size_t n, size_t alignment = 0 ) { return fc::allocate(n, alignment); }
	void deallocate_temporary( void* p, size_t size = 0 ) { fc::deallocate(n, alignment); }
#endif



FC_NAMESPACE_END

#ifdef _MSC_VER
	#pragma warning ( pop )
#endif
